import java.util.Random;

class Solution912 {
    public int[] sortArray(int[] nums) {
         pivot(nums , 0 , nums.length-1);
         return nums ;
    }

    private void pivot(int[] nums , int l , int r){
       if(l >= r) return  ; 
       // 注意left 和 right 的初始值 ;
        int key = nums[getKey(nums , l , r)] ; 
       int left = l-1 , right = r+1 ;
       for(int i=l ; i < right ; ){
          if(nums[i] < key){
            swap(nums , ++left , i++);
          }else if(nums[i] > key){
            swap(nums , --right , i);
          }else{
            i ++ ;
          }
       }
       pivot(nums , l , left) ;
       pivot(nums , right , r) ; 

    }
    private int getKey(int[] nums , int left , int right){
        Random random = new Random();
         int key = random.nextInt(right-left+1) ;
         return key+left ;
    }

    private void swap(int[]nums , int i ,int j){
        int tmp = nums[i];
        nums[i] = nums[j] ; 
        nums[j] = tmp ;
    }
}